package algorithm.search;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

import datastructure.TreeNode;
import util.DataPrinter;
import util.IntDataGenerator;

/**
 * 二叉树查找
 * @author 62121
 *
 */
public class BinaryTree {
	public static void main(String[] args) {
		int n = 100;
		int max = n*10;
		int[] data = IntDataGenerator.getRanUniqueNumArray(n, max);
		
		if(n <=1000) DataPrinter.printIntData(data);
		
		Random random = new Random();
		int tarIdx = random.nextInt(n);
		int target = data[tarIdx];
		
		System.out.println("========待查找元素==========");
		System.out.println("[" + tarIdx + "]: " + target);
		
		// 构建二叉树
		TreeNode tree = buildTree(data);

		System.out.println("========层序遍历，展示二叉树结构========"); 
		printTreeByLayer(tree);
		System.out.println("\n"); 
		
		System.out.println("========中序遍历，输出为从小到大排序的数列========"); 
		printTreeByMidOrder(tree);
		System.out.println("\n"); 
		
		long start = System.currentTimeMillis();
		int res = search(tree, target);
		
		System.out.println("========搜索结果==========");
		if(res == -1) {
			System.out.println("未找到！");
		}else {
			System.out.println("[" + res + "]: " + data[res]);
		}
		
		long end = System.currentTimeMillis();
		System.out.println("Time: " + (end-start)/1000.0);
	}
	
	/**
	 * 算法核心
	 * @param data
	 * @param tar
	 * @return
	 */
	private static int search(TreeNode tree, int tar) {
		if(tree != null) {
			if(tree.data == tar) return Integer.valueOf(tree.key);
			else if(tree.data > tar) return search(tree.left, tar);
			else return search(tree.right, tar);
		}
		return -1;
	}
	
	/**
	 * 构建二叉树
	 * @param data
	 * @return
	 */
	private static TreeNode buildTree(int[] data) {
		if (data.length <= 0) return null;
		TreeNode node = new TreeNode();
		node.data = data[0];
		node.key = String.valueOf(0);
		TreeNode tree = node;
		for(int i = 1; i < data.length ; i++) {
			TreeNode it = tree;
			while(true) {
				if(it.data > data[i]) {
					if(it.left == null) {
						TreeNode newNode = new TreeNode();
						newNode.data = data[i];
						newNode.key = String.valueOf(i);
						it.left = newNode;
						break;
					} else {
						it = it.left;
					}
				}
				else {
					if(it.right == null) {
						TreeNode newNode = new TreeNode();
						newNode.data = data[i];
						newNode.key = String.valueOf(i);
						it.right = newNode;
						break;
					} else {
						it = it.right;
					}
				}
			}

		}
		return tree;
	}
	
	/**
	 * 层序遍历并打印二叉树
	 * @param data
	 */
	private static void printTreeByLayer(TreeNode tree) {
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.offer(tree);
		
		int back = 1;
		int forward = 1;
		int cur = 1;
		while(q.size() != 0) {
			TreeNode node = (TreeNode) q.poll();
			if (node == null) {
				System.out.print("* ");
			} else {
				System.out.print("[" + node.key + "]:" + node.data + " ");
				q.offer(node.left);
				q.offer(node.right);
				forward += 2;
			}
			if(cur == back) {
				System.out.print("\n");
				back = forward;
			}
			cur ++;
		}
	}
	
	/**
	 * 中序遍历
	 * @param tree
	 */
	private static void printTreeByMidOrder(TreeNode tree) {
		if(tree == null) return;
		printTreeByMidOrder(tree.left);
		System.out.print("[" + tree.key + "]:" + tree.data + " ");
		printTreeByMidOrder(tree.right);
	}
}
